/* 
 * fft.h is Based on
 * Free FFT and convolution (C)
 * 
 * Copyright (c) 2019 Project Nayuki. (MIT License)
 * https://www.nayuki.io/page/free-small-fft-in-multiple-languages
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
 * the Software, and to permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 * - The above copyright notice and this permission notice shall be included in
 *   all copies or substantial portions of the Software.
 * - The Software is provided "as is", without warranty of any kind, express or
 *   implied, including but not limited to the warranties of merchantability,
 *   fitness for a particular purpose and noninfringement. In no event shall the
 *   authors or copyright holders be liable for any claim, damages or other
 *   liability, whether in an action of contract, tort or otherwise, arising from,
 *   out of or in connection with the Software or the use or other dealings in the
 *   Software.
 */


#include <math.h>
#include <stdint.h>

// Use table increase transform speed from 6500 tick to 2025, increase code size on 700 bytes
// Use compact table, increase code size on 208 bytes, and not decrease speed
// Used only if not defined __VNA_USE_MATH_TABLES__ (use self table for TTF or direct sin/cos calculations)
#define FFT_USE_SIN_COS_TABLE

// Use sin table and interpolation for sin/sos calculations
#ifdef __VNA_USE_MATH_TABLES__
// Use 512 table for calculation sin/cos value, also use this table for FFT
#define FAST_MATH_TABLE_SIZE 512

// Not use high part of table
#define GET_SIN_TABLE(idx) (((idx) < 256) ? sin_table_512[(idx)] : -sin_table_512[(idx)-256])

static const float sin_table_512[FAST_MATH_TABLE_SIZE/2 + 1] = {
	/*
	 * float has about 7.2 digits of precision
		for (int i = 0; i < FAST_MATH_TABLE_SIZE; i++) {
			printf("% .8f,%c", sin(2 * M_PI * i / FAST_MATH_TABLE_SIZE), i % 8 == 7 ? '\n' : ' ');
		}
	*/
	 0.00000000f, 0.01227154f, 0.02454123f, 0.03680722f, 0.04906767f, 0.06132074f, 0.07356456f, 0.08579731f,
	 0.09801714f, 0.11022221f, 0.12241068f, 0.13458071f, 0.14673047f, 0.15885814f, 0.17096189f, 0.18303989f,
	 0.19509032f, 0.20711138f, 0.21910124f, 0.23105811f, 0.24298018f, 0.25486566f, 0.26671276f, 0.27851969f,
	 0.29028468f, 0.30200595f, 0.31368174f, 0.32531029f, 0.33688985f, 0.34841868f, 0.35989504f, 0.37131719f,
	 0.38268343f, 0.39399204f, 0.40524131f, 0.41642956f, 0.42755509f, 0.43861624f, 0.44961133f, 0.46053871f,
	 0.47139674f, 0.48218377f, 0.49289819f, 0.50353838f, 0.51410274f, 0.52458968f, 0.53499762f, 0.54532499f,
	 0.55557023f, 0.56573181f, 0.57580819f, 0.58579786f, 0.59569930f, 0.60551104f, 0.61523159f, 0.62485949f,
	 0.63439328f, 0.64383154f, 0.65317284f, 0.66241578f, 0.67155895f, 0.68060100f, 0.68954054f, 0.69837625f,
	 0.70710678f, 0.71573083f, 0.72424708f, 0.73265427f, 0.74095113f, 0.74913639f, 0.75720885f, 0.76516727f,
	 0.77301045f, 0.78073723f, 0.78834643f, 0.79583690f, 0.80320753f, 0.81045720f, 0.81758481f, 0.82458930f,
	 0.83146961f, 0.83822471f, 0.84485357f, 0.85135519f, 0.85772861f, 0.86397286f, 0.87008699f, 0.87607009f,
	 0.88192126f, 0.88763962f, 0.89322430f, 0.89867447f, 0.90398929f, 0.90916798f, 0.91420976f, 0.91911385f,
	 0.92387953f, 0.92850608f, 0.93299280f, 0.93733901f, 0.94154407f, 0.94560733f, 0.94952818f, 0.95330604f,
	 0.95694034f, 0.96043052f, 0.96377607f, 0.96697647f, 0.97003125f, 0.97293995f, 0.97570213f, 0.97831737f,
	 0.98078528f, 0.98310549f, 0.98527764f, 0.98730142f, 0.98917651f, 0.99090264f, 0.99247953f, 0.99390697f,
	 0.99518473f, 0.99631261f, 0.99729046f, 0.99811811f, 0.99879546f, 0.99932238f, 0.99969882f, 0.99992470f,
	 1.00000000f, 0.99992470f, 0.99969882f, 0.99932238f, 0.99879546f, 0.99811811f, 0.99729046f, 0.99631261f,
	 0.99518473f, 0.99390697f, 0.99247953f, 0.99090264f, 0.98917651f, 0.98730142f, 0.98527764f, 0.98310549f,
	 0.98078528f, 0.97831737f, 0.97570213f, 0.97293995f, 0.97003125f, 0.96697647f, 0.96377607f, 0.96043052f,
	 0.95694034f, 0.95330604f, 0.94952818f, 0.94560733f, 0.94154407f, 0.93733901f, 0.93299280f, 0.92850608f,
	 0.92387953f, 0.91911385f, 0.91420976f, 0.90916798f, 0.90398929f, 0.89867447f, 0.89322430f, 0.88763962f,
	 0.88192126f, 0.87607009f, 0.87008699f, 0.86397286f, 0.85772861f, 0.85135519f, 0.84485357f, 0.83822471f,
	 0.83146961f, 0.82458930f, 0.81758481f, 0.81045720f, 0.80320753f, 0.79583690f, 0.78834643f, 0.78073723f,
	 0.77301045f, 0.76516727f, 0.75720885f, 0.74913639f, 0.74095113f, 0.73265427f, 0.72424708f, 0.71573083f,
	 0.70710678f, 0.69837625f, 0.68954054f, 0.68060100f, 0.67155895f, 0.66241578f, 0.65317284f, 0.64383154f,
	 0.63439328f, 0.62485949f, 0.61523159f, 0.60551104f, 0.59569930f, 0.58579786f, 0.57580819f, 0.56573181f,
	 0.55557023f, 0.54532499f, 0.53499762f, 0.52458968f, 0.51410274f, 0.50353838f, 0.49289819f, 0.48218377f,
	 0.47139674f, 0.46053871f, 0.44961133f, 0.43861624f, 0.42755509f, 0.41642956f, 0.40524131f, 0.39399204f,
	 0.38268343f, 0.37131719f, 0.35989504f, 0.34841868f, 0.33688985f, 0.32531029f, 0.31368174f, 0.30200595f,
	 0.29028468f, 0.27851969f, 0.26671276f, 0.25486566f, 0.24298018f, 0.23105811f, 0.21910124f, 0.20711138f,
	 0.19509032f, 0.18303989f, 0.17096189f, 0.15885814f, 0.14673047f, 0.13458071f, 0.12241068f, 0.11022221f,
	 0.09801714f, 0.08579731f, 0.07356456f, 0.06132074f, 0.04906767f, 0.03680722f, 0.02454123f, 0.01227154f,
	 0.00000000f,
	/*
	            -0.01227154f,-0.02454123f,-0.03680722f,-0.04906767f,-0.06132074f,-0.07356456f,-0.08579731f,
	-0.09801714f,-0.11022221f,-0.12241068f,-0.13458071f,-0.14673047f,-0.15885814f,-0.17096189f,-0.18303989f,
	-0.19509032f,-0.20711138f,-0.21910124f,-0.23105811f,-0.24298018f,-0.25486566f,-0.26671276f,-0.27851969f,
	-0.29028468f,-0.30200595f,-0.31368174f,-0.32531029f,-0.33688985f,-0.34841868f,-0.35989504f,-0.37131719f,
	-0.38268343f,-0.39399204f,-0.40524131f,-0.41642956f,-0.42755509f,-0.43861624f,-0.44961133f,-0.46053871f,
	-0.47139674f,-0.48218377f,-0.49289819f,-0.50353838f,-0.51410274f,-0.52458968f,-0.53499762f,-0.54532499f,
	-0.55557023f,-0.56573181f,-0.57580819f,-0.58579786f,-0.59569930f,-0.60551104f,-0.61523159f,-0.62485949f,
	-0.63439328f,-0.64383154f,-0.65317284f,-0.66241578f,-0.67155895f,-0.68060100f,-0.68954054f,-0.69837625f,
	-0.70710678f,-0.71573083f,-0.72424708f,-0.73265427f,-0.74095113f,-0.74913639f,-0.75720885f,-0.76516727f,
	-0.77301045f,-0.78073723f,-0.78834643f,-0.79583690f,-0.80320753f,-0.81045720f,-0.81758481f,-0.82458930f,
	-0.83146961f,-0.83822471f,-0.84485357f,-0.85135519f,-0.85772861f,-0.86397286f,-0.87008699f,-0.87607009f,
	-0.88192126f,-0.88763962f,-0.89322430f,-0.89867447f,-0.90398929f,-0.90916798f,-0.91420976f,-0.91911385f,
	-0.92387953f,-0.92850608f,-0.93299280f,-0.93733901f,-0.94154407f,-0.94560733f,-0.94952818f,-0.95330604f,
	-0.95694034f,-0.96043052f,-0.96377607f,-0.96697647f,-0.97003125f,-0.97293995f,-0.97570213f,-0.97831737f,
	-0.98078528f,-0.98310549f,-0.98527764f,-0.98730142f,-0.98917651f,-0.99090264f,-0.99247953f,-0.99390697f,
	-0.99518473f,-0.99631261f,-0.99729046f,-0.99811811f,-0.99879546f,-0.99932238f,-0.99969882f,-0.99992470f,
	-1.00000000f,-0.99992470f,-0.99969882f,-0.99932238f,-0.99879546f,-0.99811811f,-0.99729046f,-0.99631261f,
	-0.99518473f,-0.99390697f,-0.99247953f,-0.99090264f,-0.98917651f,-0.98730142f,-0.98527764f,-0.98310549f,
	-0.98078528f,-0.97831737f,-0.97570213f,-0.97293995f,-0.97003125f,-0.96697647f,-0.96377607f,-0.96043052f,
	-0.95694034f,-0.95330604f,-0.94952818f,-0.94560733f,-0.94154407f,-0.93733901f,-0.93299280f,-0.92850608f,
	-0.92387953f,-0.91911385f,-0.91420976f,-0.90916798f,-0.90398929f,-0.89867447f,-0.89322430f,-0.88763962f,
	-0.88192126f,-0.87607009f,-0.87008699f,-0.86397286f,-0.85772861f,-0.85135519f,-0.84485357f,-0.83822471f,
	-0.83146961f,-0.82458930f,-0.81758481f,-0.81045720f,-0.80320753f,-0.79583690f,-0.78834643f,-0.78073723f,
	-0.77301045f,-0.76516727f,-0.75720885f,-0.74913639f,-0.74095113f,-0.73265427f,-0.72424708f,-0.71573083f,
	-0.70710678f,-0.69837625f,-0.68954054f,-0.68060100f,-0.67155895f,-0.66241578f,-0.65317284f,-0.64383154f,
	-0.63439328f,-0.62485949f,-0.61523159f,-0.60551104f,-0.59569930f,-0.58579786f,-0.57580819f,-0.56573181f,
	-0.55557023f,-0.54532499f,-0.53499762f,-0.52458968f,-0.51410274f,-0.50353838f,-0.49289819f,-0.48218377f,
	-0.47139674f,-0.46053871f,-0.44961133f,-0.43861624f,-0.42755509f,-0.41642956f,-0.40524131f,-0.39399204f,
	-0.38268343f,-0.37131719f,-0.35989504f,-0.34841868f,-0.33688985f,-0.32531029f,-0.31368174f,-0.30200595f,
	-0.29028468f,-0.27851969f,-0.26671276f,-0.25486566f,-0.24298018f,-0.23105811f,-0.21910124f,-0.20711138f,
	-0.19509032f,-0.18303989f,-0.17096189f,-0.15885814f,-0.14673047f,-0.13458071f,-0.12241068f,-0.11022221f,
	-0.09801714f,-0.08579731f,-0.07356456f,-0.06132074f,-0.04906767f,-0.03680722f,-0.02454123f,-0.01227154f,
	-0.00000000f*/
};
// 
#if FFT_SIZE == 256
#define FFT_SIN(i) sin_table_512[    2*(i)]
#define FFT_COS(i) ((i) >  64 ?-sin_table_512[2*(i)-128] : sin_table_512[128-2*(i)])
#elif FFT_SIZE == 512
#define FFT_SIN(i) sin_table_512[      (i)]
#define FFT_COS(i) ((i) > 128 ?-sin_table_512[  (i)-128] : sin_table_512[128-  (i)])
#else
#error "Need use bigger sin/cos table for new FFT size"
#endif

#else
#ifdef FFT_USE_SIN_COS_TABLE
#if FFT_SIZE == 256
static const float sin_table_256[] = {
	/*
	 * float has about 7.2 digits of precision
		for (uint8_t i = 0; i < FFT_SIZE - (FFT_SIZE / 4); i++) {
			printf("% .8f,%c", sin(2 * M_PI * i / FFT_SIZE), i % 8 == 7 ? '\n' : ' ');
		}
	*/
	 // for FFT_SIZE = 256
	 0.00000000,  0.02454123,  0.04906767,  0.07356456,  0.09801714,  0.12241068,  0.14673047,  0.17096189,
	 0.19509032,  0.21910124,  0.24298018,  0.26671276,  0.29028468,  0.31368174,  0.33688985,  0.35989504,
	 0.38268343,  0.40524131,  0.42755509,  0.44961133,  0.47139674,  0.49289819,  0.51410274,  0.53499762,
	 0.55557023,  0.57580819,  0.59569930,  0.61523159,  0.63439328,  0.65317284,  0.67155895,  0.68954054,
	 0.70710678,  0.72424708,  0.74095113,  0.75720885,  0.77301045,  0.78834643,  0.80320753,  0.81758481,
	 0.83146961,  0.84485357,  0.85772861,  0.87008699,  0.88192126,  0.89322430,  0.90398929,  0.91420976,
	 0.92387953,  0.93299280,  0.94154407,  0.94952818,  0.95694034,  0.96377607,  0.97003125,  0.97570213,
	 0.98078528,  0.98527764,  0.98917651,  0.99247953,  0.99518473,  0.99729046,  0.99879546,  0.99969882,
	 1.00000000,/*  0.99969882,  0.99879546,  0.99729046,  0.99518473,  0.99247953,  0.98917651,  0.98527764,
	 0.98078528,  0.97570213,  0.97003125,  0.96377607,  0.95694034,  0.94952818,  0.94154407,  0.93299280,
	 0.92387953,  0.91420976,  0.90398929,  0.89322430,  0.88192126,  0.87008699,  0.85772861,  0.84485357,
	 0.83146961,  0.81758481,  0.80320753,  0.78834643,  0.77301045,  0.75720885,  0.74095113,  0.72424708,
	 0.70710678,  0.68954054,  0.67155895,  0.65317284,  0.63439328,  0.61523159,  0.59569930,  0.57580819,
	 0.55557023,  0.53499762,  0.51410274,  0.49289819,  0.47139674,  0.44961133,  0.42755509,  0.40524131,
	 0.38268343,  0.35989504,  0.33688985,  0.31368174,  0.29028468,  0.26671276,  0.24298018,  0.21910124,
	 0.19509032,  0.17096189,  0.14673047,  0.12241068,  0.09801714,  0.07356456,  0.04906767,  0.02454123,
	 0.00000000, -0.02454123, -0.04906767, -0.07356456, -0.09801714, -0.12241068, -0.14673047, -0.17096189,
	-0.19509032, -0.21910124, -0.24298018, -0.26671276, -0.29028468, -0.31368174, -0.33688985, -0.35989504,
	-0.38268343, -0.40524131, -0.42755509, -0.44961133, -0.47139674, -0.49289819, -0.51410274, -0.53499762,
	-0.55557023, -0.57580819, -0.59569930, -0.61523159, -0.63439328, -0.65317284, -0.67155895, -0.68954054,
	-0.70710678, -0.72424708, -0.74095113, -0.75720885, -0.77301045, -0.78834643, -0.80320753, -0.81758481,
	-0.83146961, -0.84485357, -0.85772861, -0.87008699, -0.88192126, -0.89322430, -0.90398929, -0.91420976,
	-0.92387953, -0.93299280, -0.94154407, -0.94952818, -0.95694034, -0.96377607, -0.97003125, -0.97570213,
	-0.98078528, -0.98527764, -0.98917651, -0.99247953, -0.99518473, -0.99729046, -0.99879546, -0.99969882,*/
};
// full size table:
//   sin = sin_table_256[i   ]
//   cos = sin_table_256[i+64]
//#define FFT_SIN(i) sin_table_256[(i)]
//#define FFT_COS(i) sin_table_256[(i)+64]

// for size use only 0-64 indexes
//   sin = i > 64 ? sin_table_256[128-i] : sin_table_256[   i];
//   cos = i > 64 ?-sin_table_256[ i-64] : sin_table_256[64-i];
#define FFT_SIN(i) ((i) > 64 ? sin_table_256[128-(i)] : sin_table_256[   (i)])
#define FFT_COS(i) ((i) > 64 ?-sin_table_256[ (i)-64] : sin_table_256[64-(i)])

#elif FFT_SIZE == 512
static const float sin_table_512[] = {
	/*
	 * float has about 7.2 digits of precision
		for (int i = 0; i < FFT_SIZE - (FFT_SIZE / 4); i++) {
			printf("% .8f,%c", sin(2 * M_PI * i / FFT_SIZE), i % 8 == 7 ? '\n' : ' ');
		}
	*/
	 // For FFT_SIZE = 512
	 0.00000000,  0.01227154,  0.02454123,  0.03680722,  0.04906767,  0.06132074,  0.07356456,  0.08579731,
	 0.09801714,  0.11022221,  0.12241068,  0.13458071,  0.14673047,  0.15885814,  0.17096189,  0.18303989,
	 0.19509032,  0.20711138,  0.21910124,  0.23105811,  0.24298018,  0.25486566,  0.26671276,  0.27851969,
	 0.29028468,  0.30200595,  0.31368174,  0.32531029,  0.33688985,  0.34841868,  0.35989504,  0.37131719,
	 0.38268343,  0.39399204,  0.40524131,  0.41642956,  0.42755509,  0.43861624,  0.44961133,  0.46053871,
	 0.47139674,  0.48218377,  0.49289819,  0.50353838,  0.51410274,  0.52458968,  0.53499762,  0.54532499,
	 0.55557023,  0.56573181,  0.57580819,  0.58579786,  0.59569930,  0.60551104,  0.61523159,  0.62485949,
	 0.63439328,  0.64383154,  0.65317284,  0.66241578,  0.67155895,  0.68060100,  0.68954054,  0.69837625,
	 0.70710678,  0.71573083,  0.72424708,  0.73265427,  0.74095113,  0.74913639,  0.75720885,  0.76516727,
	 0.77301045,  0.78073723,  0.78834643,  0.79583690,  0.80320753,  0.81045720,  0.81758481,  0.82458930,
	 0.83146961,  0.83822471,  0.84485357,  0.85135519,  0.85772861,  0.86397286,  0.87008699,  0.87607009,
	 0.88192126,  0.88763962,  0.89322430,  0.89867447,  0.90398929,  0.90916798,  0.91420976,  0.91911385,
	 0.92387953,  0.92850608,  0.93299280,  0.93733901,  0.94154407,  0.94560733,  0.94952818,  0.95330604,
	 0.95694034,  0.96043052,  0.96377607,  0.96697647,  0.97003125,  0.97293995,  0.97570213,  0.97831737,
	 0.98078528,  0.98310549,  0.98527764,  0.98730142,  0.98917651,  0.99090264,  0.99247953,  0.99390697,
	 0.99518473,  0.99631261,  0.99729046,  0.99811811,  0.99879546,  0.99932238,  0.99969882,  0.99992470,
	 1.00000000,/*  0.99992470,  0.99969882,  0.99932238,  0.99879546,  0.99811811,  0.99729046,  0.99631261,
	 0.99518473,  0.99390697,  0.99247953,  0.99090264,  0.98917651,  0.98730142,  0.98527764,  0.98310549,
	 0.98078528,  0.97831737,  0.97570213,  0.97293995,  0.97003125,  0.96697647,  0.96377607,  0.96043052,
	 0.95694034,  0.95330604,  0.94952818,  0.94560733,  0.94154407,  0.93733901,  0.93299280,  0.92850608,
	 0.92387953,  0.91911385,  0.91420976,  0.90916798,  0.90398929,  0.89867447,  0.89322430,  0.88763962,
	 0.88192126,  0.87607009,  0.87008699,  0.86397286,  0.85772861,  0.85135519,  0.84485357,  0.83822471,
	 0.83146961,  0.82458930,  0.81758481,  0.81045720,  0.80320753,  0.79583690,  0.78834643,  0.78073723,
	 0.77301045,  0.76516727,  0.75720885,  0.74913639,  0.74095113,  0.73265427,  0.72424708,  0.71573083,
	 0.70710678,  0.69837625,  0.68954054,  0.68060100,  0.67155895,  0.66241578,  0.65317284,  0.64383154,
	 0.63439328,  0.62485949,  0.61523159,  0.60551104,  0.59569930,  0.58579786,  0.57580819,  0.56573181,
	 0.55557023,  0.54532499,  0.53499762,  0.52458968,  0.51410274,  0.50353838,  0.49289819,  0.48218377,
	 0.47139674,  0.46053871,  0.44961133,  0.43861624,  0.42755509,  0.41642956,  0.40524131,  0.39399204,
	 0.38268343,  0.37131719,  0.35989504,  0.34841868,  0.33688985,  0.32531029,  0.31368174,  0.30200595,
	 0.29028468,  0.27851969,  0.26671276,  0.25486566,  0.24298018,  0.23105811,  0.21910124,  0.20711138,
	 0.19509032,  0.18303989,  0.17096189,  0.15885814,  0.14673047,  0.13458071,  0.12241068,  0.11022221,
	 0.09801714,  0.08579731,  0.07356456,  0.06132074,  0.04906767,  0.03680722,  0.02454123,  0.01227154,
	 0.00000000, -0.01227154, -0.02454123, -0.03680722, -0.04906767, -0.06132074, -0.07356456, -0.08579731,
	-0.09801714, -0.11022221, -0.12241068, -0.13458071, -0.14673047, -0.15885814, -0.17096189, -0.18303989,
	-0.19509032, -0.20711138, -0.21910124, -0.23105811, -0.24298018, -0.25486566, -0.26671276, -0.27851969,
	-0.29028468, -0.30200595, -0.31368174, -0.32531029, -0.33688985, -0.34841868, -0.35989504, -0.37131719,
	-0.38268343, -0.39399204, -0.40524131, -0.41642956, -0.42755509, -0.43861624, -0.44961133, -0.46053871,
	-0.47139674, -0.48218377, -0.49289819, -0.50353838, -0.51410274, -0.52458968, -0.53499762, -0.54532499,
	-0.55557023, -0.56573181, -0.57580819, -0.58579786, -0.59569930, -0.60551104, -0.61523159, -0.62485949,
	-0.63439328, -0.64383154, -0.65317284, -0.66241578, -0.67155895, -0.68060100, -0.68954054, -0.69837625,
	-0.70710678, -0.71573083, -0.72424708, -0.73265427, -0.74095113, -0.74913639, -0.75720885, -0.76516727,
	-0.77301045, -0.78073723, -0.78834643, -0.79583690, -0.80320753, -0.81045720, -0.81758481, -0.82458930,
	-0.83146961, -0.83822471, -0.84485357, -0.85135519, -0.85772861, -0.86397286, -0.87008699, -0.87607009,
	-0.88192126, -0.88763962, -0.89322430, -0.89867447, -0.90398929, -0.90916798, -0.91420976, -0.91911385,
	-0.92387953, -0.92850608, -0.93299280, -0.93733901, -0.94154407, -0.94560733, -0.94952818, -0.95330604,
	-0.95694034, -0.96043052, -0.96377607, -0.96697647, -0.97003125, -0.97293995, -0.97570213, -0.97831737,
	-0.98078528, -0.98310549, -0.98527764, -0.98730142, -0.98917651, -0.99090264, -0.99247953, -0.99390697,
	-0.99518473, -0.99631261, -0.99729046, -0.99811811, -0.99879546, -0.99932238, -0.99969882, -0.99992470*/
};
// full size table:
//   sin = sin_table_512[i    ]
//   cos = sin_table_512[i+128]
//#define FFT_SIN(i) sin_table_512[(i)    ]
//#define FFT_COS(i) sin_table_512[(i)+128]

// for size use only 0-128 indexes
//   sin = i > 128 ? sin_table_512[256-i] : sin_table_512[    i];
//   cos = i > 128 ?-sin_table_512[i-128] : sin_table_512[128-i];
#define FFT_SIN(i) ((i) > 128 ? sin_table_512[256-(i)] : sin_table_512[    (i)])
#define FFT_COS(i) ((i) > 128 ?-sin_table_512[(i)-128] : sin_table_512[128-(i)])

#else
#error "Need build table for new FFT size"
#endif

#else
// Not use FFT_USE_SIN_COS_TABLE, use direct sin/cos calculations
#define FFT_SIN(k) sin(2 * VNA_PI * (k) / FFT_SIZE)
#define FFT_COS(k) cos(2 * VNA_PI * (k) / FFT_SIZE);

#endif // FFT_USE_SIN_COS_TABLE

#endif // __VNA_USE_MATH_TABLES__

static uint16_t reverse_bits(uint16_t x, int n) {
	uint16_t result = 0;
	int i;
	for (i = 0; i < n; i++, x >>= 1)
		result = (result << 1) | (x & 1U);
	return result;
}

/***
 * dir = forward: 0, inverse: 1
 * https://www.nayuki.io/res/free-small-fft-in-multiple-languages/fft.c
 */
static void fft(float array[][2], const uint8_t dir) {
// FFT_SIZE = 2^FFT_N
#if   FFT_SIZE == 256
 #define FFT_N     8
#elif FFT_SIZE == 512
 #define FFT_N     9
#else
 #error "Need define FFT_N for this FFT size"
#endif
	const uint16_t n = FFT_SIZE;
	const uint8_t levels = FFT_N; // log2(n)

	const uint8_t real =   dir & 1;
	const uint8_t imag = ~real & 1;
	uint16_t i;

	for (i = 0; i < n; i++) {
		uint16_t j = reverse_bits(i, levels);
		if (j > i) {
			float temp = array[i][real];
			array[i][real] = array[j][real];
			array[j][real] = temp;
			temp = array[i][imag];
			array[i][imag] = array[j][imag];
			array[j][imag] = temp;
		}
	}
	const uint16_t size = 2;
	uint16_t halfsize = size / 2;
	uint16_t tablestep = n / size;
	uint16_t j, k;
	// Cooley-Tukey decimation-in-time radix-2 FFT
	for (;tablestep; tablestep>>=1, halfsize<<=1) {
		for (i = 0; i < n; i+=2*halfsize) {
			for (j = i, k = 0; j < i + halfsize; j++, k += tablestep) {
				uint16_t l = j + halfsize;
				float s = FFT_SIN(k);
				float c = FFT_COS(k);
				float tpre =  array[l][real] * c + array[l][imag] * s;
				float tpim = -array[l][real] * s + array[l][imag] * c;
				array[l][real] = array[j][real] - tpre;
				array[l][imag] = array[j][imag] - tpim;
				array[j][real] += tpre;
				array[j][imag] += tpim;
			}
		}
	}
}

static inline void fft_forward(float array[][2]) {
	fft(array, 0);
}

static inline void fft_inverse(float array[][2]) {
	fft(array, 1);
}

// Return sin/cos value angle in range 0.0 to 1.0 (0 is 0 degree, 1 is 360 degree)
void vna_sin_cos(float angle, float * pSinVal, float * pCosVal)
{
#ifndef __VNA_USE_MATH_TABLES__
  // Use default sin/cos functions
  angle *= 2 * VNA_PI;   // Convert to rad
  *pSinVal = sin(angle);
  *pCosVal = cos(angle);
#else
  const float Dn = 2 * VNA_PI / FAST_MATH_TABLE_SIZE; // delta between the two points in table (fixed);
  uint16_t indexS, indexC;  // Index variable
  float f1, f2, d1, d2;     // Two nearest output values
  float Df, fract, temp;

  // Round angle to range 0.0 to 1.0
  temp = fabsf(angle);
  temp-= (uint32_t)temp;//floorf(temp);
  // Scale input from range 0.0 to 1.0 to table size
  temp*= FAST_MATH_TABLE_SIZE;

  indexS = temp;
  indexC = indexS + (FAST_MATH_TABLE_SIZE / 4); // cosine add 0.25 (pi/2) to read from sine table
  // Calculation of fractional value
  fract  = temp - indexS;
  // Align indexes to table
  indexS&= (FAST_MATH_TABLE_SIZE-1);
  indexC&= (FAST_MATH_TABLE_SIZE-1);

  // Read two nearest values of input value from the cos & sin tables
#if 0
  f1 = GET_SIN_TABLE(indexC  );
  f2 = GET_SIN_TABLE(indexC+1);
  d1 = GET_SIN_TABLE(indexS  );
  d2 = GET_SIN_TABLE(indexS+1);
#else
  if (indexC < 256){f1 = sin_table_512[indexC    +0];f2 = sin_table_512[indexC    +1];}
  else             {f1 =-sin_table_512[indexC-256+0];f2 =-sin_table_512[indexC-256+1];}
  if (indexS < 256){d1 = sin_table_512[indexS    +0];d2 = sin_table_512[indexS    +1];}
  else             {d1 =-sin_table_512[indexS-256+0];d2 =-sin_table_512[indexS-256+1];}
#endif

  // Calculation of cosine value
  Df = f2 - f1;          // delta between the values of the functions
  temp = Dn * (d1 + d2) + 2 * Df;
  temp = (3 * Df + (d2 + 2 * d1) * Dn) - fract * temp;
  temp = fract * temp - d1 * Dn;
  *pCosVal = fract * temp + f1;

  // Calculation of sine value
  Df = d2 - d1; // delta between the values of the functions
  temp = Dn * (f1 + f2) - 2 * Df;
  temp = fract * temp + (3 * Df - (f2 + 2 * f1) * Dn);
  temp = fract * temp + f1 * Dn;
  *pSinVal = fract * temp + d1;
  if (angle < 0)
    *pSinVal = -*pSinVal;
#endif
}
